#
# @lc app=leetcode.cn id=1249 lang=python3
#
# [1249] 移除无效的括号
#

# @lc code=start
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        # 时间复杂度过高
        # def isValid(s):
        #     cnt = 0
        #     for ch in s:
        #         match ch:
        #             case '(':
        #                 cnt += 1
        #             case ')':
        #                 cnt -= 1
        #         if cnt < 0:
        #             return False
        #     return cnt == 0
        
        # str_set = {s}
        # while True:
        #     valid_list = list(filter(isValid, str_set))
        #     if valid_list:
        #         return valid_list[0]
            
        #     new_str_set = set()
        #     for ss in str_set:
        #         for i in range(len(ss)):
        #             if ss[i] in '()':
        #                 new_str_set.add(ss[:i]+ss[i+1:])
        #     str_set = new_str_set 
        # 核心思想:用栈来匹配括号对
        idx_to_remove = set()
        stack = []
        for idx, ch in enumerate(s):
            if ch not in '()': # 非括号字符
                continue
            # ()
            if ch == '(':
                stack.append(idx)
            elif not stack: # 栈为空,没有和右括号)匹配的左括号(
                idx_to_remove.add(idx)
            else: # ch==')且栈不为空,有和右括号匹配的左括号
                stack.pop() 
        # 并集,栈中还剩余的左括号
        idx_to_remove = idx_to_remove.union(set(stack))
        # 删除无效括号字符
        str_buffer = []
        for idx, ch in enumerate(s):
            if idx not in idx_to_remove:
                str_buffer.append(ch)
        return "".join(str_buffer)

# @lc code=end

